/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.util.iterators;

import java.util.EmptyStackException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

/** Class capable of generating all segmentations of an (integer length) line. The
 *  number of segments and constraints (min/max length) for each segment may be 
 *  given.
 */
public class SegmentationGenerator implements Iterable<int[]> {
	/** Number of segements. */
	private int segments;
	/** Length of line to be segmented. */
	private int length;
	/** For each segment, the minimum length. */
	private int[] min;
	/** For each segment, the maximum length. */
	private int[] max;
	/** minLeft[i]=min[i]+...+min[segments-1] */
	private int[] minLeft;
	/** maxLeft[i]=max[i]+...+max[segments-1] */
	private int[] maxLeft;
	
	public SegmentationGenerator(int length, int max[], int min[]) {
		this.length=length;
		if (max.length!=min.length) throw new IllegalArgumentException();
		this.segments=max.length;
		this.max=max;
		this.min=min;
		minLeft=new int[segments+1];
		maxLeft=new int[segments+1];
		for (int i=segments-1; i>=0; --i) {
			if ((min[i]>max[i]) || (min[i]<0)) throw new IllegalArgumentException("Expected: 0<=min<=max");
			minLeft[i]=minLeft[i+1]+min[i];
			maxLeft[i]=maxLeft[i+1]+max[i];
		}
	}
	
	public SegmentationGenerator(int length, int max[]) {
		this(length,max,new int[max.length]);
	}
	
	public SegmentationGenerator(int length, int segments) {
		this.length=length;
		this.segments=segments;
		max=new int[segments];
		for (int i=0; i<segments; ++i) max[i]=length;
		min=new int[segments];
		minLeft=new int[segments+1];
		maxLeft=new int[segments+1];
		for (int i=segments-1; i>=0; --i) maxLeft[i]=maxLeft[i+1]+max[i];
	}

	public Iterator<int[]> iterator() {
		return new SegmentationIterator();
	}
	
	private static class State {
		/** (Unfinished) segmentation. */
		private int[] current;
		/** Position in current segmentation to be increased next. */
		private int pos;
		/** Maximal value for pos. */
		private int max;
		/** Length left to be distributed. */
		private int left;
	}
	
	private class SegmentationIterator implements Iterator<int[]> {
		Stack<State> stack;
		
		public SegmentationIterator() {
			// check if there exists at least one sequence
			if ((length<minLeft[0])||(length>maxLeft[0])) {
				stack=null;
				return;
			}
			stack = new Stack<State>();
			int[] current = new int[segments];
			State state = new State();
			state.pos = 0;
			state.max = Math.min(max[0], length-minLeft[1]);
			current[0] = Math.max(min[0], length-maxLeft[1]);
			state.current = current;
			state.left = length-current[0];
			stack.push(state);
			for (int pos=1; pos<segments; ++pos) {
				state = pushNewState(state);
			}
		}

		private State pushNewState(State lastState) {
			State state = new State();
			int pos = lastState.pos+1;
			state.pos = pos;
			state.max = Math.min(max[pos], lastState.left-minLeft[pos+1]);
			state.current = new int[segments];
			System.arraycopy(lastState.current, 0, state.current, 0, segments);
			int value = Math.max(min[pos], lastState.left-maxLeft[pos+1]);
			state.current[pos]=value;
			state.left=lastState.left-value;
			stack.push(state);
			return state;
		}
		
		public boolean hasNext() {
			return stack!=null;
		}

		public int[] next() {
			if (stack==null) throw new NoSuchElementException();
			State state = stack.pop();
			int[] result = state.current;
			while (state.current[state.pos]==state.max) {
				try {
					state = stack.pop();
				} catch (EmptyStackException e) {
					stack=null;
					return result;
				}
			}
			state.current[state.pos]+=1;
			state.left-=1;
			stack.push(state);
			while (stack.size()<segments) {
				state = pushNewState(state);
			}
			return result;
		}

		public void remove() { throw new UnsupportedOperationException(); }
	}
}
